package hyy_2022;

import commons.TreeNode;

/**
 * 另一棵树的子树
 */
public class _0810_572_IsSubTree {

    public boolean isSubTree(TreeNode s, TreeNode t) {
        //t为null,一定都是true
        if(t == null) {
            return true;
        }
        //s为null,一定是false
        if(s == null) {
            return false;
        }
        //t为s的左子树 || t为s的右子树 || t与s相等
        return isSubTree(s.left,t) || isSubTree(s.right,t) ||  isSameTree(s,t);

    }

    /**
     * 判断两棵树是否相等
     * 1、两棵树都为空, 则两棵树相等
     * 2、两棵树中任一棵树为空,则两棵树不相等
     * 3、两棵树根节点的值不相等,则两棵树不相等
     * 4、比较两棵树的左子树是否相等、两棵树的右子树是否相等
     * @param s
     * @param t
     * @return boolean
     */
    public boolean isSameTree(TreeNode s, TreeNode t) {
        if(s == null && t == null) {
            return true;
        }
        if(s == null || t == null) {
            return false;
        }
        if(s.val != t.val) {
            return false;
        }
        return isSameTree(s.left,t.left) && isSameTree(s.right,t.right);
    }
}
